package may;

import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-25 15:09
 * https://leetcode-cn.com/problems/out-of-boundary-paths/  出界的路径数
 * 状态表 : 从1-N步的可能出界的情况个数以及在当前位置移动一次会不会造成出界 使用备忘录+剪枝因为会出现重复的位置
 * 状态转移
 * @description：
 * @modified By：
 * @version:
 */
public class May25 {

    private Integer[][][] memo;
    private int[] offsets = new int[] {0,1,0,-1,0};
    /**
     * create by: 冯涛滔
     * description: TODO
     * create time: 2020-5-25 15:12
     * @params [m, n, N, i, j] m行*n列的网格 球初始化在i,j 最多可以移动N次
     * @return int
     */
    public int findPaths(int m, int n, int N, int i, int j) {
        if(N==0) return 0;
        int mod = 1000000007;
        int[][] direct = {{1,0},{-1,0},{0,1},{0,-1}};
        int[][] dp = new int[m][n];
        for(int k=0;k<N;k++){
            int[][] tmp = new int[m][n];
            for(int x=0;x<m;x++){
                for(int y=0;y<n;y++){
                    for(int[] d: direct){
                        if(x+d[0]<0 || x+d[0]>=m || y+d[1]<0 || y+d[1]>=n){
                            tmp[x][y]++;
                        }else{
                            tmp[x][y] = (tmp[x][y]+dp[x+d[0]][y+d[1]])%mod;
                        }
                    }
                }
            }
            dp = tmp;
        }
        return dp[i][j];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/unique-paths/ 不同路径
     * 状态表法
     * 走到某个位置的走法是他的上面一个位置的走法+左边位置的走法
     * 状态转移公式: i,x个位置的走法 = i-1,x + i,x-1
     * 初始化 第一行和第一列的走法都只有一种
     * create time: 2020-5-25 16:47
     * @params [m, n]
     * @return int
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n ; i++) {//初始化第一行
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {//初始化第一列
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {//从第二行开始 减少运算
            for (int j = 1; j < dp[0].length; j++) { //每行从第二哥开始算减少运算
                dp[i][j] = dp[i-1][j] + dp[i][j-1];//上面一格的路数+左边一格的路数
            }
        }
        return dp[m-1][n-1];
    }
    //加强版有障碍物
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        dp[0][0] = 1;
        for (int i = 1; i < obstacleGrid[0].length ; i++) {//初始化第一行
            if(obstacleGrid[0][i]==1){
                dp[0][i] = 0;
            }else{
                dp[0][i] = dp[0][i-1];
            }
        }

        for (int i = 1; i < obstacleGrid.length; i++) {//初始化第一列
            if(obstacleGrid[i][0]==1){
                dp[i][0] = 0;
            }else{
                dp[i][0] = dp[i-1][0];
            }
        }
        for (int i = 1; i < dp.length; i++) {//从第二行开始 减少运算
            for (int j = 1; j < dp[0].length; j++) { //每行从第二哥开始算减少运算
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];//上面一格的路数+左边一格的路数
                }
            }
        }
        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
    public static void main(String[] args) {
        May25 a = new May25();
        int[][] list = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(a.uniquePathsWithObstacles(list));
    }
}
